package 力扣.树.中序遍历;

public class 恢复二叉搜索树99 {
    /**
      二叉搜索树中序遍历本质就是一个有序数组。
     本题就是让我们找出造成有序数组非有序的两个元素，交换它们即可。
     注意下面两个例子：[10,2,3,4,5,1]、[10,2,20,30,40,50]
     [10,2,20,30,40,50]：10、2可以立刻交换
     [10,2,3,4,5,1]:需要遍历到最后一个元素最后一个元素才能进行交换
     正如上面两个例子而言，我们需要保存 （10，2）这两个变量 ，然后遍历整个数组。
                       看看是否仍然存在非有序情况：若存在：则让（10、1）交换，若不存在则再让（10、2）进行交换
     */
    public void recoverTree(TreeNode root) {
          if (root == null){
              return;
          }
          midDfs(root);
          if (preValue2 != null){
              int te = preValue3.val;
              preValue3.val = preValue2.val;
              preValue2.val = te;
          }
    }
    private TreeNode preValue = null;
    private TreeNode preValue2 = null;
    private TreeNode preValue3 = null;
    private void  midDfs(TreeNode root){
        if (root != null){
            midDfs(root.left);
            if (preValue != null){
                if (Long.valueOf(root.val) - preValue.val < 0){
                     if (preValue2 == null){//第一次找到非法顺序
                         preValue2 = preValue;
                         preValue3 = root;
                     }else {//第二次找到非法顺序
                         int te = root.val;
                         root.val = preValue2.val;
                         preValue2.val = te;
                         preValue2 = null;
                         return;
                     }

                }
            }
            preValue = root;
            midDfs(root.right);
        }
    }

    public void recoverTree2(TreeNode root) {

    }

}
